class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length == 1) return;

        int n = nums.length;
        int i, j = n - 1;
        for (i = n-1; i > 0; i--){
            if (nums[i] > nums[i-1]){
                j = i - 1;
                break;
            }
        }

        if (j < i){
            int k;
            for (k = n-1; k > i;k-- ){
                if (nums[k] > nums[j]){
                    break;
                }
            }
            swap(nums, j, k);
        } else {
            i = 0;
        }

        

        while (i < n-1){
            swap(nums, i, n-1);
            i++;
            n--;
        }

    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}